/**
 * 在一个二维数组中(每一维数组的长度相同),每一行都按照从左到右递增的顺序排序 ,
 * 每一列都按照从上到下递增顺序的顺序排序
 * 请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数
 */

/**
 * 找到一行中最大的数/最小的数 , 再将要查找的数和这个数进行比较
 * 一次排除一行或者一列
 * 1 2 3 ④
 * 2 3 4 5
 * ③ 4 5 6
 * 如上, 找出数组中的4,4在第一行中最大,在最后一列最小
 * 3 在第一列中最大 ,在最后一行中最小
 *
 */
public class suanfa01 {

    public boolean Find(int target, int[][] array) {
        if (array == null) {
            return false;
        }
        int i = 0;
        int j = array[0].length - 1;
        while (i < array.length && j >= 0) {
            if (target < array[i][j]) {//array[i][j] 一定是当前列最小的,当前行最大的
                j--;//消除当前列
            } else if (target > array[i][j]) {
                i++;//消除当前行
            } else {
                return true;
            }
        }
        return false;
    }
}
